

\chapter{Linux内存映射}

\section{进入保护模式}
在进入开始介绍内存管理之前，我们需要让我们的系统进入保护模式并开启分页机制，虽然这部分内容如果使用C语言来写应该非常的简单，但这部分内容确实使用汇编语言实现，这绝对不是为了让读者看起来很cool。采用这种技术是有原因，理解这个原因是非常重要的。

在保护模式下，程序有了4G的寻址空间（其实这个问题比较复杂，很难一两句说清楚，在内存管理部分我们再详细的讲）。Linux内核将4G空间划分成了两个部分，用户控件（0G～3G）及内核空间（3G～4G）。vmlinux在加载的时候其实并不位于3G～4G空间之上。
原因包括多个：首先PC机并未启动分页机制，它能访问的是物理内存，而无力内存有没有4G很难说。第二及时真的有4G内存，在进入保护模式之前，16位的程序也没有办法访问到这些物理内存。

因此Linux采用了一个很精巧的办法，将vmlinux加载到低端内存。再启动分页机制后将它映射到高端内存上。这对C程序来说绝对是个挑战，因为从链接的时刻各个符号的地址已经确定了，如果要写两个模式下运行的程序，每看到一个符号叫要想想现在处于什么模式，究竟是以物理内存还是用虚拟内存的方式访问这个符号。如果是以物理内存的方式访问，还要进行指针运行而后在进行类型转换，想想都头大。

简单的做法是写一段汇编代码，这段代码之后就进入分页模式，C程序向怎么写就怎么写；再次之前就要讲过一些运算了，不过这段代码比较短，整体还是可以接受的。由于进入内核之前必须先执行这段代码，因此这段代码的名字就叫做head.S（完整路径是arch/i386/kernel/head.S）。我们的代码做了很大简化，感兴趣的同学可以对比，具体代码如下:
\begin{lstlisting}
	
\end{lstlisting}
这部代码就是Linux进入保护模式的代码，从当中可以看到Linux包含两部分的

当中还是包含很多将来要用的东西的，比如cpu\_gdt\_table。 在系统初始化阶段Linux采用boot\_gdt\_table。在正式启动之后将会切换到cpu\_gdt\_table上来。

好了到现在为止我们的系统已经进入了保护模式，接下来我们逐个初始化操作系统的子系统。


\section{构建新的内核}

内核是有汇编和C联合编写的，与寻常的程序不同，我们不能简单的ld \$(LDFLAGS) fileslist -o vmlinux，而使使用一种叫做ldscript的脚本。 ld script提供了非常有用的功能，使我们在编写内核的时候更简单:
1. 制定不同段的位置
2. 将多个段合并成一个段
3. 初始化全局变量

在启动分页机制的时候大家注意到了变量pg，它保存了全局页表，当将它放在那里呢？最好的位置是程序的尾部，但在链接之前我们是不知道程序的尾部在那里，不过没关系，ld script可以告诉我们。
\begin{lstlisting}[language=bash]


\end{lstlisting}


\subsection{ldscript}
ldscript非常的容易

\subsection{模仿Linux的机制}
Linux调用lds并不像我们介绍的那么简单直接，因为它真的做了一些使的代码更容易维护的事情。但为了提高维护性，我们必须提高我们对工具的使用能力才行。
首先来介绍一下linux使用lds的方式，它并不直接使用lds文件，而是使用一种叫做lds.S的文件之后来生成lds文件，为什么这么作呢，因为linux希望所有的变量都统一的放在一个地方，而不是分散在各地。但是lds是不支持包含C语言的头文件的。但是.S文件支持，即GAS格式的汇编语言文件。

GAS格式的汇编文件有两种.s和.S，这两种文件有一个微小的不同，虽然微小但足够让你崩溃一天。.s和.S的文件都支持gcc或者as进行汇编，但是.s的文件是直接忽略include指令的，是的直接忽略还不报错，让你误以为引入了都文件但实际上没有。如果你在你的汇编程序中用到了某个\#define定义的常量，它也不报语法错误，而是报undefined symbol。这个错误如此具有误导性，以至于我会怀疑C语言通过\#define定义的常量会包含在symbol table当中。但实际上完全不会，它仅仅是没有包含头文件而已，把扩展名换成.S立时所有的问题都没有了。



Intel提供了多级分页的机制，上面介绍的是3级分页， 对于x86-64系统，Intel提供了4级分页。在32位系统下，如果不启用PAE，仅仅对1G空间进行寻址，CPU可以使用2级分页。此外Intel还提供了扩展分页，这是一种以4M作为一页的分页方式。Linux定义了几个概念和结构题用来区别多级页表机制当中各个级别的名字。

\begin{itemize}
  \item PTE(Page Table Entry)
  \item PMD(Page Middle Directory)
  \item PUD(Page Upper Directory)
  \item PGD(Page Global Directory)
\end{itemize}

\subsection{初始化}

\begin{lstlisting}
\end{lstlisting}

其中pg0代表一个安全的位置，即pg0处的内存既没有代码也没有数据，是一块可以用的物理内存。
如何才知道自己程序和数据的尾部处于内存的什么位置呢， GLD(我们常用的链接程序, GNU ld)提供了这么一种能力，我们可以在连接脚本加入一些变量，这些变量会被链接程序当作符号加载到ELF文件当中。
这也就是为啥我们可以在arch/i386/mm/pgtable.h当中看到pg0的声明，却总找不到它定义在那个代码文件当中的原因。

还有一个问题为什么每个值都要减去\_\_PAGE\_OFFSET呢，这个值有代表一个非常大的值。
这个原因也可以从链接脚本当中找到， 在链接脚本的开始出我们可以发现这个脚本指定的其实地址是\_\_PAGE\_OFFSET + 0x100000。
但实际上在初始化阶段我们将它仅仅加载到了0x100000。
之后我们通过映射的方式将它们映射到\_\_PAGE\_OFFSET + 0x100000这里，之后的代码就可以顺利运行了。
通过这机制也可以保证此后所有的内核代码都是处于0xC0000000之上的，与我们之前的约定一致。
在启动虚拟内存之前，我们访问任何一个vmlinux上的符号，都必须使用它的物理地址，即虚拟地址-0xC0000000。
在启用虚拟内存之后，我们就可以完全使用C程序来实现了。

这也就是为什么这么一段简单的程序要使用汇编语言实现，而不用C程序实现了。

常量 \_\_PAGE\_OFFSET定义了内核空间所处的位置，这个位置是虚拟地址，对于32位系统来说是4G当中最高的那1G，即0xC00000000～0xFFFFFFFF。
在Linux下，这部分地址全部交由内核来使用，应用程序是无法直接访问的，而且对于所有的应用程序这部分的地址的内容是一样的。

变量swapper\_pg\_dir是一个有1024项的数组，他就是我们初始化阶段的PGD。

后边的代码就比较容易看懂了，就是不断的填满这1024项。


有一个问题不知道读者发现了没有，这段代码如果使用C语言来实现的话应该是非常容易的是什么原因导致它没有这么做呢？

这段代码执行完毕后，我们已经完成从0开始到8M部分的初始化。

\subsection{FAQ}
为何32位地址总线却只能提供30位的寻址能力？

\section{Init Pagging}

在架构相关的初始化真正开始时，page table的映射才开始建立，他的入口在paging\_init函数。
这个函数定义在文件arch/i386/mm/init.c

\begin{lstlisting}[language=C]
static void __init pagetable_init(void) {
  u32 addr;
  pgd_t *pgd_base = swapper_pg_dir;

  // if PSE available
  kernel_physical_mapping_init(pgd_base);
}

void __init paging_init(void) {
  pagetable_init();

  load_cr3(swapper_pg_dir);

  __flush_tlb_all();

  kmap_init();
  zone_sizes_init();
}
\end{lstlisting}


真正负责页表初始化的是kernel\_physical\_mapping\_init, 他负责PGD, PMD和PTE三级页表的初始化。
它的逻辑非常简单。
需要注意的一定是PGD一定是连续的1024项，但是PMD和PTE就不一定了，如果上一级的页表项没有用，那么下一级根本就不需要分配空间。
这部分细节藏在函数one\_md\_table\_init和函数one\_page\_table\_init当中。
\begin{lstlisting}[language=C]
/*
 * This maps the physical memory to kernel virtual 
 * address space, a total of max_low_pfn pages, by 
 * creating page tables starting from address
 * PAGE_OFFSET.
 */
static void __init kernel_physical_mapping_init(pgd_t *pgd_base) {
  u32 pfn;
  pgd_t *pgd;
  pmd_t *pmd;
  pte_t *pte;

  int pgd_idx, pmd_idx, pte_ofs;

  pgd_idx = pgd_index(PAGE_OFFSET);
  pgd = pgd_base + pgd_idx;
  pfn = 0;

  for (; pgd_idx < PTRS_PER_PGD; pgd++, pgd_idx++) {
    pmd = one_md_table_init(pgd);

    if (pfn >= max_low_pfn) {
      continue;
    }

    for (pmd_idx = 0; pmd_idx < PTRS_PER_PMD && pfn < max_low_pfn;
         pmd++, pmd_idx++) {
      pte = one_page_table_init(pmd);
      for (pte_ofs = 0; pte_ofs < PTRS_PER_PTE && pfn < max_low_pfn;
           pte++, pfn++, pte_ofs++) {
        if (is_kernel_text(address)) {
          set_pte(pte, pfn_pte(pfn, PAGE_KERNEL_EXEC));
        } else {
          set_pte(pte, pfn_pte(pfn, PAGE_KERNEL);
        }
      }
    }
  }
}
\end{lstlisting}


\section{Page分配及释放}
 这一节的名字是内存的分配与释放，其实这已经包含了所有内存管理的内容。
之所以起这个名字而非内存管理，是希望给大家一个动态的感觉：我们是以分配及释放的过程来讲述这部分内容的。

内核本身占用的物理内存并不多，内核将空闲的page都分区域保存起来,这个区域就是zone。
当内核试图分配内存时会挑选合适的区域分配若干个page并对page分配线性地址，之后linux还要更新页表。
这个过程就是Linux分配内存的过程。


整个过程最复杂的部分在于挑选合适的页，这个过程也是分层次的， 最底层以内存大小为目标进行分配，这个系统的叫做“伙伴系统”。
再上一层是“面向对象”的，这个对象从C语言的角度看就是结构体，简单的理解就是建立一组内存缓冲区，缓冲区的key是结构体， 当某个结构体释放时内存将放回到这个结构体的缓冲当中，分配时则尽量从缓冲区分配，否则使用下一层的“伙伴系统”进行分配。
除了slab之外，Linux还有其他策略。
这些策略针对不同体系的机器，各有特斯，以后我们会逐一比较。
从上面的描述的过程来看，这里面涉及到几个核心的概念，我们逐一的介绍。

\subsection{page}
page经常被翻译做页框，它是以4K为单元的物理内存单元(当然也可能是2M，与CPU的分页模式有关)。
每一个page都有一个描述符与之对应，它保存着page的信息。


在内核完成映射之后，我们实际上占用了所有的物理内存。
\subsection{Zone}

\subsubsection{HighMemory}
内核内存从0xC000000 + 0x100000开始，0～3G的内存交给用户控件使用，而32位机器既能够寻址的最大范围是4G，再高的内存就没有办法映射了。
其他的内存就只能放在High Memroy区域了。
这部分内存的特点是，他们没有进行映射，需要的时候才进行映射。

\subsection{page的分配与释放}


\section{x86分页模式}

\subsection{反汇编}
在启用分页之后，反汇编将变得有些令人迷惑。在启动分页模式之前，调试总是针对物理地址的，这时候使用的指令是hbreak；启动分页模式之后，如果依然按照之前的方法进行，读者一定会发现与地址相关的值是转换为硬件地址之后的值，而非虚拟地址，这多少会令人疑惑分页机制到底启用没有。没关系，验证的方法总是有的，通过反汇编虚拟地址是一个不错的办法。

使用gdb对虚拟地址进行反汇编
\begin{lstlisting}
(gdb) disas 0xc0100000,+100
Dump of assembler code from 0xc0100000 to 0xc0100064:
   0xc0100000 <startup_32+0>:   cld
   0xc0100001 <startup_32+1>:   lgdtl  0x100294
   0xc0100008 <startup_32+8>:   mov    $0x10,%eax
   0xc010000d <startup_32+13>:  mov    %eax,%ds
   0xc010000f <startup_32+15>:  mov    %eax,%es
   0xc0100011 <startup_32+17>:  mov    %eax,%fs
   0xc0100013 <startup_32+19>:  mov    %eax,%gs
   0xc0100015 <startup_32+21>:  mov    %eax,%ss
   0xc0100017 <startup_32+23>:  mov    $0x105000,%edi
   0xc010001c <startup_32+28>:  mov    $0x101000,%edx
   0xc0100021 <startup_32+33>:  mov    $0x7,%eax
   0xc0100026 <startup_32+38>:  lea    0x7(%edi),%ecx
   0xc0100029 <startup_32+41>:  mov    %ecx,(%edx)
   0xc010002b <startup_32+43>:  mov    %ecx,0xc00(%edx)
   0xc0100031 <startup_32+49>:  add    $0x4,%edx
   0xc0100034 <startup_32+52>:  mov    $0x400,%ecx
   0xc0100039 <startup_32+57>:  stos   %eax,%es:(%edi)
   0xc010003a <startup_32+58>:  add    $0x1000,%eax
   0xc010003f <startup_32+63>:  loop   0xc0100039 <startup_32+57>
   0xc0100041 <startup_32+65>:  lea    0x20007(%edi),%ebp
   0xc0100047 <startup_32+71>:  cmp    %ebp,%eax
   0xc0100049 <startup_32+73>:  jb     0xc0100026 <startup_32+38>
   0xc010004b <startup_32+75>:  mov    %edi,0x1002a0
   0xc0100051 <startup_32+81>:  mov    $0x101000,%eax
   0xc0100056 <startup_32+86>:  mov    %eax,%cr3
   0xc0100059 <startup_32+89>:  mov    %cr0,%eax
   0xc010005c <startup_32+92>:  or     $0x80000000,%eax
   0xc0100061 <startup_32+97>:  mov    %eax,%cr0
End of assembler dump.
\end{lstlisting}


使用gdb对物理地址进行反汇编
\begin{lstlisting}
(gdb) disas 0x100000,+100
Dump of assembler code from 0x100000 to 0x100064:
=> 0x00100000:  cld
   0x00100001:  lgdtl  0x1000fc
   0x00100008:  mov    $0x18,%eax
   0x0010000d:  mov    %eax,%ds
   0x0010000f:  mov    %eax,%es
   0x00100011:  mov    %eax,%fs
   0x00100013:  mov    %eax,%gs
   0x00100015:  mov    %eax,%ss
   0x00100017:  mov    $0x104000,%edi
   0x0010001c:  mov    $0x101000,%edx
   0x00100021:  mov    $0x7,%eax
   0x00100026:  lea    0x7(%edi),%ecx
   0x00100029:  mov    %ecx,(%edx)
   0x0010002b:  mov    %ecx,0xc00(%edx)
   0x00100031:  add    $0x4,%edx
   0x00100034:  mov    $0x400,%ecx
   0x00100039:  stos   %eax,%es:(%edi)
   0x0010003a:  add    $0x1000,%eax
   0x0010003f:  loop   0x100039
   0x00100041:  lea    0x20007(%edi),%ebp
   0x00100047:  cmp    %ebp,%eax
   0x00100049:  jb     0x100026
   0x0010004b:  mov    %edi,0x100108
   0x00100051:  mov    $0x101000,%eax
   0x00100056:  mov    %eax,%cr3
   0x00100059:  mov    %cr0,%eax
   0x0010005c:  or     $0x80000000,%eax
   0x00100061:  mov    %eax,%cr0
End of assembler dump.
\end{lstlisting}

对比结果可以很明显的发现其中的差别，针对虚拟地址的反汇编的地址值基本都是0xC001****格式的，因为gdb做了一些转换工作，如果不知道这种转换的存在，相信调试者一定会很迷惑。因为作者就曾经很迷惑：到底分页机制启用了没有。作者还尝试使用objdump的反汇编结果与物理地址反汇编结果向对比，差别于此类似，当却让作者开始怀疑虚拟机的正确性。还有“交叉验证”的方式总是能够帮助更进一步的理解问题。
